double x[maxn], y[maxn], a[maxn];

void calcFi(int i) {
	double si = y[i], a0[maxn];
	memset(a0, 0, sizeof(a0));
	a0[0] = 1;
	for (int j = 0; j < n; ++ j) {
		if (j != i) {
			si = si / (x[j] - x[i]);
		}
		for (int k = n - 1; k > 0; -- k) {
			a0[k] = a0[k] * (-x[j]) + a0[k - 1];
		}
		a0[0] *= (-x[j]);
	}
	for (int j = 0; j < n; ++ j) {
		a[j] += a0[j] * si;
	}
}

int main() {
	memset(a, 0, sizeof(a));
	for (int i = 0; i < n; ++ i) {
		calcFi(i);
	}
}
